package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.*;

public class _3_Solution {

    @Test
    public void test(){
        int[][] envelopes = {{15,8},{2,20},{2,14},{4,17},{8,19},{8,9},{5,7},{11,19},{8,11},{13,11},{2,13},{11,19},{8,11},{13,11},{2,13},{11,19},{16,1},{18,13},{14,17},{18,19}};
        System.out.println(maxEnvelopes(envelopes));
    }

    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (o1, o2) -> {
            if (o1[0] > o2[0]) {
                return 1;
            } else if (o1[0] < o2[0]) {
                return -1;
            } else {
                return o2[1]-o1[1];
            }
        });
        List<Integer> lenList = new ArrayList<>();
        lenList.add(envelopes[0][1]);
        for (int i = 1; i < envelopes.length; i++) {
            int h = envelopes[i][1];
            if (h > lenList.get(lenList.size() - 1)) {
                lenList.add(h);
            }else if(h != lenList.get(lenList.size() - 1)){
                int index = this.binarySearch(lenList, h);
                lenList.set(index,h);
            }
        }
        return lenList.size();

    }

    private int binarySearch(List<Integer> lenList, int h) {
        int low = 0;
        int high = lenList.size()-1;
        while (low <= high) {
            int mid = (low+high)/2;
            Integer value = lenList.get(mid);
            if (value > h) {
                high = mid - 1;
            } else if (value == h){
                return mid;
            }else {
                low = mid + 1;
            }
        }
        return low;
    }
}
